#include <vector>

using namespace std;

void ShellSort(vector<int>& array)
{
    int n = array.size();
    int gap = n / 2;
    while(gap > 1)
    {
        for(int i = 0; i < n - gap; i++)
        {
            int end = i, tmp = array[i + gap];
            while(end >= 0)
            {
                if(tmp < array[end])
                {
                    array[end + gap] = array[end];
                    end -= gap;
                }
                else break;
            }
            array[end + gap] = tmp;
        }
        gap = gap / 2;
    }

}